package leetcode.editor.cn.dsa17_traversal;
//给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
//
// 示例 ： 
// 输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
//       5
//      / \
//    3    6
//   / \    \
//  2   4    8
// /        / \ 
//1        7   9
//
// 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
//          \
//           6
//            \
//             7
//              \
//               8
//                \
//                 9  
//
// 
//
// 提示： 
// 给定树中的结点数介于 1 和 100 之间。
// 每个结点都有一个从 0 到 1000 范围内的唯一整数值。 
// 
// Related Topics 树 深度优先搜索 递归 
// 👍 126 👎 0

import java.util.ArrayList;
import java.util.List;

public class IncreasingOrderSearchTree897 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public TreeNode increasingBST(TreeNode root) {
            if (root == null) return root;
            List<TreeNode> list = new ArrayList<>();
            inOrderTree(root, list); // 递归遍历二叉树，拿到中序遍历序列
            for (int i = 0; i < list.size() - 1; i++) {
                // 让每个节点右子树指向下一个节点，左子树为空
                TreeNode treeNode = list.get(i);
                treeNode.left = null;
                treeNode.right = list.get(i+1);
            }
            // 处理最后一个节点，左右子树都为空
            TreeNode treeNode = list.get(list.size() - 1);
            treeNode.left = null;
            treeNode.right = null;
            return list.get(0); // 返回中序序列的首节点
        }

        private void inOrderTree(TreeNode root, List<TreeNode> list) {
            // 处理二叉树为空的边界问题
            // 结束条件：遍历指针已经到达叶子节点下一层，可以返回
            if (root == null) return;
            inOrderTree(root.left, list); // 先遍历左子树节点
            list.add(root); // 访问根节点
            inOrderTree(root.right, list); // 再遍历右子树节点
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
